package greedy;

import java.util.ArrayList;
import java.util.Arrays;

/**
 * 455.分发饼干
 * 376.摆动序列
 * 53.最大子序和
 * 122买卖股票的最佳时机II
 * 55.跳跃游戏
 * 45.跳跃游戏II
 * 1005.K次取反后最大化的数组和
 * 134.加油站
 * 135.分发糖果
 * 860柠檬水找零
 * 406.根据身高重建队列
 * 406.根据身高重建队列（续集）
 * 452.用最少数量的箭引爆气球
 * 435.无重叠区间
 * 763.划分字母区间
 * 56.合并区间
 * 738.单调递增的数字
 * 714.买卖股票的最佳时机含手续费
 * 968.我要监控二叉树！
 *
 */



class 分发饼干_455_重做版 {
    public int findContentChildren(int[] g, int[] s) {
        Arrays.sort(s);
        Arrays.sort(g);
        int i=0, j=0, res=0;
        // 贪心模板  ： 不断尝试  用小的匹配大的
        // 双指针
        //  while () { 最小的饼干能满足当前胃口的孩子 res ++  否则用大点的饼干来喂当前的孩子 }
        while(i < s.length && j < g.length) {
            if(s[i] >= g[j]) {
                i ++;
                j ++;
                res ++;
            } else {
                i ++;
            }
        }

        return res;
    }
}
public class 分发饼干_455 {
    public int findContentChildren(int[] g, int[] s) {
        int count = 0;
        Arrays.sort(g);
        Arrays.sort(s);
        // 对每块饼干s[j]
        // 看满不满足小孩 g[i]需求 g[i] <= s[j] 满足都++  不满足说明最小的饼干比最小胃口小， 饼干++
        // 因为当前最小的饼干比最小的小孩胃口小 ，只能换个大点的饼干试下
        for (int i = 0, j = 0; j < s.length && i < g.length; i++, j++) {
            while (i< g.length && g[i] > s[j] ) {
                j++;
            }
            if (i< g.length && g[i] <= s[j]) {
                count++;
            }

        }
        return count;
    }

    public static void main(String[] args) {
        分发饼干_455 a = new 分发饼干_455();
        a.findContentChildren(new int[]{7, 8, 9, 10}, new int[]{5, 6, 7, 8});
        System.out.println(a);

    }
}
